/**
 * 手动实现一个哈希表：可以作为一个缓存层使用
 *      （1）哈希表本质是一个存储链表的数组
 *      （2）链表数组中，每一个小标里面都存储着一个单链表
 */
public class HashTableDemo {
    public static void main(String[] args) {
        //测试哈希表
        HashTable hashTable = new HashTable(9);
        //添加一个元素
//        hashTable.addEmp(new Emp(31,"tom"));
//        hashTable.addEmp(new Emp(22,"jom"));
//        hashTable.addEmp(new Emp(5,"hom"));
//        hashTable.addEmp(new Emp(68,"张三"));
//        hashTable.addEmp(new Emp(19,"lom"));
//        hashTable.addEmp(new Emp(21,"lom"));
//        hashTable.addEmp(new Emp(41,"kom"));
//        hashTable.addEmp(new Emp(51,"kom"));
//        hashTable.addEmp(new Emp(61,"kom"));
//        hashTable.addEmp(new Emp(71,"kom"));

        //自动按照顺序添加元素
        hashTable.addEmpById(new Emp(21,"tom"));
        hashTable.addEmpById(new Emp(11,"tom"));
        hashTable.addEmpById(new Emp(1,"tom"));
        hashTable.addEmpById(new Emp(1,"tom"));
        //打印哈希表
        hashTable.listHashTab();
        System.out.println("--------------------------");

        //查找某个员工，根据id值
        int id = 51;
        Emp empById = hashTable.findEmpById(id);
        System.out.println("查找编号为"+id+"的员工信息："+empById);
        System.out.println("--------------------------");

        //根据id值删除一个员工
        hashTable.deleteEmpById(5);
        Emp empById1 = hashTable.findEmpById(5);
        System.out.println(empById1);
    }
}
//创建一个哈希表
class HashTable{
    //定义一个值为单链表数组的最大存储数，遍历时需要用到
    public int maxSize;

    //创建一个单链表数组，用于存放单链表,单链表数组必须初始化，即，链表的第一个值不能为null值
    public SingleLinkedList[] singleLinkedListArray;

    //构造方法
    public HashTable(int maxSize) {
        this.maxSize = maxSize;
        //创建一个指定大小的哈希表
        this.singleLinkedListArray = new SingleLinkedList[this.maxSize];
        //循环初始化，单链表的第一个值
        for (int i = 0; i < this.maxSize; i++) {
            singleLinkedListArray[i] = new SingleLinkedList();
        }
    }

    //创建散列函数，目的是为了根据用户id，方便快速的计算出某个数据，应该添加到哪个链表中去，散列函数写法不固定
    public int hashFunction(Emp emp){
        //本人这里使用取模法
        return emp.id % 10 - 1;//返回的就是这个员工对应链表的下标值
    }

    //创建散列函数，目的是为了根据用户id，方便快速的计算出某个数据，应该添加到哪个链表中去，散列函数写法不固定
    public int hashFunction(int id){
        //本人这里使用取模法
        return id % 10 - 1;//返回的就是这个员工对应链表的下标值
    }

    //创建添加某个员工的方法，不会自动按照顺序添加元素
    public void addEmp(Emp emp){
        //先根据员工id的散列函数值，确定员工应该所在的链表id值
        int i = hashFunction(emp);
        //调用单链表的添加方法，进行添加元素
        singleLinkedListArray[i].add(emp);
    }

    //创建添加某个员工的方法，会自动按照顺序添加元素
    public void addEmpById(Emp emp){
        //调用散列函数，找到元素应该被添加的位置
        int i = hashFunction(emp);
        //调用单链表的自动按照顺序添加方法，进行添加元素
        singleLinkedListArray[i].addById(emp);
    }


    //打印哈希表
    public void listHashTab(){
        //将每一个链表都要循环遍历打印
        for (int i = 0; i < maxSize; i++) {
            //每个链表再分别调用打印方法
            System.out.println("第"+(i+1)+"个链表：");
            singleLinkedListArray[i].list();
            //换行
            System.out.println();
        }
    }

    //根据id查找员工信息
    public Emp findEmpById(int id){
        //调用散列函数，判断id所在的链表
        int i = hashFunction(id);
        //调用单链表的查询方法
        Emp emp = singleLinkedListArray[i].selectById(id);
        return emp;
    }

    //根据员工id删除员工信息
    public void deleteEmpById(int id){
        //调用散列函数，找到id对应的链表
        int i = hashFunction(id);
        singleLinkedListArray[i].deleteById(id);
    }
}

//创建一个链表，作为哈希表的添加元素
class SingleLinkedList{
    //创建一个表头,必须初始化头节点，只不过头节点里面的数据为空，注意头节点不是直接为null
    private Emp head = new Emp();

    //创建一个添加元素的方法(按照添加顺序排序，不会自动从大到小排序)
    public void add(Emp emp){
        //如果是第一个元素，直接添加进去
        if (head.next == null) {
            head.next = emp;
            return;//结束方法
        }
        //不是第一个添加元素，需要找到链表最后
        //创建辅助指针
        Emp temp = head;
        while (true) {
            if (temp.next == null) {
                temp.next = emp;
                break;
            }
            temp = temp.next;   //后移指针
        }

    }

    //创建一个会自动按照元素id的顺序进行添加的方法（会自动排序从小到大）
    public void addById(Emp emp){
        //如果是第一个元素，直接添加进去
        if (head.next == null) {
            head.next = emp;
            return;//结束方法
        }
        //若不是第一个元素
        //创建辅助指针
        Emp temp = head;
        while (true){//遍历寻找待插入值的前一个节点
            if (temp.next == null) {
                //若找到最后，则添加到链表最后
                temp.next = emp;
                break;
            }
            if (temp.next.id > emp.id) {
                //此时temp就是被添加元素的前一个节点
                emp.next = temp.next;
                temp.next = emp;
                break;
            }else if (temp.next.id == emp.id){
                System.out.println("编号"+emp.id+"重复，不能添加成功！");
                break;
            }
            temp = temp.next;//后移指针
        }

    }

    //遍历整个链表的显示方法
    public void list(){
        //若链表为空，则给出提示
        if (head.next == null) {
            System.out.println("链表为空，没有数据可以遍历输出！");
        }else {
            //若链表不为空，则遍历打印
            Emp temp = head.next;
            while (true){
                System.out.println(temp);
                //若遍历到最后，就退出循环
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;//后移指针
            }
        }
    }

    //根据id查找某个员工
    public Emp selectById(int id){
        //创建辅助指针
        Emp temp = head;
        //遍历查找
        while (true){
            if (temp.next == null) {
                //遍历到最后，说明没有这个员工
                System.out.println("哈希表中不存在编号为："+id+"的员工！");
                break;
            }
            if (temp.next.id == id) {
                //找个这个员工，结束循环
                break;
            }
            temp = temp.next;//后移指针
        }
        return temp.next;
    }

    //根据id删除一个员工
    public void deleteById(int id){
        //创建头指针的辅助指针
        Emp temp = head;
        if (temp.next == null) {
            System.out.println("链表为空，没有可以删除的员工信息！");
            return;
        }
        while (true){
            if (temp.next == null) {
                System.out.println("链表不存在该员工信息！没有必要再次删除！");
                break;
            }
            if (temp.next.id == id) {
                //若找到这个员工信息
                temp.next = temp.next.next;
                break;
            }
            temp = temp.next.next;
        }
    }
}

//创建单链表的添加元素
class Emp{
    public int id;//编号
    public String name;//姓名
    public Emp next;//存储下一个同类对象，默认为空

    public Emp() {
    }

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name +
                '}';
    }
}